package com.company.other;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 145. 二叉树的后序遍历
 * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：root = [1,null,2,3]
 * 输出：[3,2,1]
 * 示例 2：
 *
 * 输入：root = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：root = [1]
 * 输出：[1]
 *
 *
 * 提示：
 *
 * 树中节点的数目在范围 [0, 100] 内
 * -100 <= Node.val <= 100
 *
 *
 * 进阶：递归算法很简单，你可以通过迭代算法完成吗？
 * */
public class PostorderTraversal {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    /**
     *
     * 方法： 栈-后序遍历二叉树
     * 步骤：
     *      1.从根节点开始，判断根节点是否为空，不为空入栈，指向左孩子，继续执行1，直到左孩子为空
     *      2.读取栈顶节点，如果这个节点的右孩子不为空且没有被访问，继续执行1，否则出栈并访问，继续执行2
     *      如何判断当前节点的右孩子是否被访问？
     *          保存上一次访问过的节点，如果右孩子与上一次访问过的节点相同，那么右孩子已经被访问
     *      终止条件：当前引用节点为空，且栈空
     *
     *      错误写法：
     *      问题出在，当栈顶元素为空的时候，构成死循环，应当在确定栈顶元素的右孩子为非空且未被访问之后才能指向栈顶元素的右孩子
     *          public List<Integer> postorderTraversal(TreeNode root) {
     *         List<Integer> res = new ArrayList<>();
     *         Stack<TreeNode> stack = new Stack<>();
     *         TreeNode lastVistNode = null;
     *         while(root != null || !stack.isEmpty()){
     *             if(root != null){
     *                 if(root != lastVistNode){
     *                     stack.push(root);
     *                     root = root.left;
     *                 }else{
     *                     root = stack.pop();
     *                     res.add(root.val);
     *                     lastVistNode = root;
     *                     root = null;
     *                 }
     *             }else{
     *                 root = stack.peek();
     *                 root = root.right;
     *             }
     *         }
     *         return res;
     *     }
     * */
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode lastVistNode = null;
        while(root != null || !stack.isEmpty()){
            if(root != null){
                stack.push(root);
                root = root.left;
            }else{
                root = stack.peek();
                if(root.right != null && root.right != lastVistNode){
                    root = root.right;
                    stack.push(root);
                    root = root.left;
                }else{
                    root = stack.pop();
                    res.add(root.val);
                    lastVistNode = root;
                    root = null;
                }
            }
        }
        return res;
    }
}
